#include<iostream>
#include<vector>
#include<unordered_map>
#include<string>
using namespace std;

//vector<int> rearrangeBarcodes(vector<int>& barcodes) {
//    vector<int> mn;
//    int max = 0, curmax = 0;
//    int cur = barcodes[0];
//    int flag = barcodes[0];
//    for (auto x : barcodes)
//    {
//        if (x == cur) curmax++;
//        else
//        {
//            if (curmax > max) max = curmax, flag = x - 1;
//
//            cur = x;
//            curmax = 1;
//        }
//    }
//    curmax = 0;
//    cur = barcodes[0];
//    for (auto x : barcodes)
//    {
//        if (x == cur) curmax++;
//        else
//        {
//            if (curmax == max) mn.push_back(x - 1);
//            cur = x;
//            curmax = 1;
//        }
//    }
//    if (curmax == max) mn.push_back(cur);
//    vector<int> ret(barcodes.size());
//    int n = mn.size();
//    int z = 0;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < barcodes.size(); j++)
//        {
//            if (barcodes[j] == mn[i])
//            {
//                if (z < barcodes.size())
//                {
//                    ret[z] = barcodes[j];
//                    z += 2;
//                }
//                else z = 1;
//            }
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < barcodes.size(); j++)
//        {
//            if (barcodes[j] != mn[i])
//            {
//                ret[z] = barcodes[j];
//                z += 2;
//            }
//        }
//    }
//    return ret;
//}
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
    unordered_map<int, int> hash;
    int maxV = 0, maxC = 0;
    for (auto x : barcodes)
    {
        if (maxC < ++hash[x])
        {
            maxC = hash[x];
            maxV = x;
        }
    }
    vector<int> ret(barcodes.size());
    int index = 0;
    for (int i = 0; i < maxC; i++)
    {
        ret[index] = maxV;
        index += 2;
    }
    hash.erase(maxV);
    unordered_map<int, int>::iterator it = hash.begin();
    /*for (auto& [x, y] : hash)
    {
        for (int i = 0; i < y; i++)
        {
            if (index > ret.size() - 1) index = 1;
            ret[index] = x;
            index += 2;
        }
    }*/
    for (auto i = it; i != hash.end(); i++)
    {
        for (int j = 0; j < it->second; j++)
        {
            if (index > ret.size() - 1) index = 1;
            ret[index] = it->first;
            index += 2;
        }
    }
    return ret;
}

string reorganizeString(string s) {
    unordered_map<char, int> hash;
    int maxC = 0;
    char maxV = ' ';
    for (int i = 0; i < s.size(); i++)
    {
        if(maxC< ++hash[s[i]])
    }
    for (auto x : s)
    {
        if (maxC < ++hash[x]) maxC = hash[x], maxV = x;
    }
    int n = s.size();
    if (maxC > (n + 1) / 2) return " ";
    string ret;
    ret.resize(n);
    int index = 0;
    for (int i = 0; i < maxC; i++)
    {
        ret[index] = maxV;
        index += 2;
    }
    hash.erase("maxV");
    /*for (auto& [x, y] : hash)
    {
        for (int i = 0; i < y; i++)
        {
            if (index >= n) index = 1;
            ret[index] = 'x';
            index += 2;
        }
    }*/
    return ret;
}

int main()
{
	vector<int> v{ 1,1,1,1,3,4,2,2,2,2,5 };
	/*int flag = 0;
	for (auto x : v)
	{
		if (x > flag) flag = x + 1;
	}*/
    /*rearrangeBarcodes(v);
    string s;
    s.resize(2);
    s[0] = 's';*/
    reorganizeString("aab");
	return 0;
}